#include <stdio.h>
#include <stdlib.h>

/*数据结构定义*/
typedef int DataType;
typedef struct
{
    DataType *data; //用于存放待排序关键字的起始地址
    int NUM; //待排序关键字的个数
} SortObject;

typedef struct node //用于表插入排序的数据结构
{
    DataType  info;
    struct node *next;
} linkObject;

//输出顺序表
void print(SortObject *p)
{
    for(int i=0;i<p->NUM;i++)
        printf("%d ",p->data[i]);
    printf("\n");
}

//输出链表
void printLink(linkObject *Head)
{
    linkObject *p = Head->next ;
    while(p)
    {
        printf("%d ",p->info);
        p = p->next;
    }
    printf("\n");
}

/*第一关
此处请填写代码实现递增序进行直接插入排序,
 要求每趟排序后 调用print函数，输出关键字的排列情况*/
void insertSort( SortObject *Rec )
{

    /*----begin------*/
    for (int i = 1; i < Rec->NUM; i++)
    {
        int temp = Rec->data[i];
        for (int j = i - 1; temp < Rec->data[j] && j >= 0; j--)
        {
            Rec->data[j + 1] = Rec->data[j];
            //  if(j!=i-1) Rec->data[j+1] = temp;
            Rec->data[j] = temp;
        }
        print(Rec);
    }



    /*-----end------*/

}

/*第二关
此处请填写代码实现递增序进行二分插入排序,

  实质是在已经有序的表中采用二分法查找插入位置
  要求每趟排序后 调用print函数，输出关键字的排列情况*/
void binInsertSort(  SortObject *Rec )
{
    /*----begin------*/
    int high, low,mid,temp;
    for (int i = 1; i < Rec->NUM; i++)
    {
        temp = Rec->data[i];
        low = 0;
        high = i - 1;

        while (low <= high)
        {
            mid = (low + high) / 2;
            if (temp < Rec->data[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        for (int j = i - 1; j >= low; j--)
        {
            Rec->data[j + 1] = Rec->data[j];
        }
        Rec->data[low] = temp;
        print(Rec);
    }

    /*-----end------*/

}

/* 第四关
此处请填写代码实现递增序进行shell排序,

  要求每趟排序后 调用print函数，输出关键字的排列情况
  */
void shellSort( SortObject *Rec,int d )
{
    int temp,i,j;
    int inc;
    for (inc = d; inc > 0; inc = inc / 2)
    {
        for ( i = inc; i < Rec->NUM; i++)
        {
            temp = Rec->data[i];
            for ( j = i - inc; j >= 0 && temp <Rec->data[j]; j -= inc)
            {
                Rec->data[j + inc] = Rec->data[j];
            }
            Rec->data[j + inc] = temp;
        }
        print(Rec);
    }

}

/*第三关
此处请填写代码实现递增序进行表插入排序,
  返回值是关键字比较次数
  Head是表头结点，不存放数据，info是待插入数据
  要求每趟排序后 调用printLink函数，输出关键字的排列情况
  */
void listSort(linkObject *plist )
{

    /*----begin------*/
    linkObject* now, * pf, * p, * q;
    linkObject* head = plist;
    pf = head->next;

    if (pf == NULL) return;

    now = pf->next;

    if (now == NULL) return;

    while (now!=NULL)
    {
        q = head;
        p = head->next;
        while (p!=now && p->info <= now->info)
        {
            q = p;
            p = p->next;
        }
        if (p == now)
        {
            pf = pf->next;
            now = pf->next;
            printLink(plist);
            continue;
        }
        pf->next = now->next;
        q->next = now;
        now->next = p;
        now = pf->next;
        printLink(plist);
    }

    /*-----end------*/

}
